package Year22_Month05.day06;

public class 实现strStr_KMP {
    public int strStr(String haystack, String needle) {
        //先进行检测，如果模式串或者说是主串有一个为Null,那么就直接返回0
        if(haystack.length() == 0 || needle.length() == 0){
            return 0;
        }
        //定义一个长度和needle也就是模式串长度相同的int数组来进行next数组的存储
        int[] next = new int[needle.length()];
        //调用next()来进行next数组的获取
        next(needle,next);
        //定义指针j来遍历模式串
        int j = -1;
        for (int i = 0; i < haystack.length(); i++) {
            //如果说模式串和主串不相同，那么就根据next数组的指示来进行回退
            while(j >= 0 && haystack.charAt(i) != needle.charAt(j+1)){
                j = next[j];
            }
            //如果模式串和主串相同那么就同时移动i指针和j指针
            if(haystack.charAt(i) == needle.charAt(j+1)){
                j++;
            }
            //如果说遍历模式串的j指针当前下标已经来到了模式串的末尾，那么就证明模式串被子串包含，返回主串对应的下标即可
            if(j == needle.length() - 1){
                return (i - needle.length() + 1);
            }
        }
        //如果最后没找到就返回-1
        return -1;
    }

    public void next(String needle,int[] next){
        int j = -1;//首先初始化j为-1
        next[0] = j;//next[0]初始化为j
        for (int i = 1; i < needle.length(); i++) {
            //如果说此时不相等就回退
            while(j >= 0 && needle.charAt(i) != needle.charAt(j+1)){
                j = next[j];
            }
            //相等的话前缀和后缀指针就同时往后走
            if(needle.charAt(i) == needle.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }
}
